//
// Created by mazaiting on 2024/4/27.
//

#include <bits/stdc++.h>

using namespace std;

const int init_cap = 5;       //顺序表的初始容量（5）
template<typename T>
class SqList           //顺序表类模板
{
public:
    T *data;           //存放顺序表元素空间的指针
    int capacity;           //顺序表的容量
    int length;       //存放顺序表的长度
    //线性表的基本运算算法

    SqList()               //构造函数
    {
        data = new T[init_cap];       //为data分配初始容量大小的空间
        capacity = init_cap;       //初始化容量
        length = 0;           //初始时置length为0
    }

    SqList(const SqList<T> &s)    //初始化复制构造函数
    {
        capacity = s.capacity;        //复制容量
        length = s.length;        //复制长度
        data = new T[capacity];    //为当前顺序表分配空间
        for (int i = 0; i < length; i++)    //元素复制
            data[i] = s->data[i];
    }

    ~SqList()        //析构函数
    {
        delete[] data;    //释放data指向的空间
    }


    void recap(int new_cap)            //改变顺序表的容量为new_cap
    {
        if (new_cap <= 0) return;
        T *old_data = data;
        data = new T[new_cap];            //分配新空间
        capacity = new_cap;            //更新容量
        for (int i = 0; i < length; i++)        //元素复制
            data[i] = old_data[i];
        delete[] old_data;            //释放原空间
    }

    void CreateList(T a[], int n)          //由数组a中元素整体建立顺序表
    {
        for (int i = 0; i < n; i++) {
            if (length < capacity)          //容量不够时
                recap(2 * length);          //扩大容量
            data[length] = a[i];
            length++;                  //添加后元素个数增加1
        }
    }

    void Add(T e)            //在线性表的末尾添加一个元素e
    {
        if (length == capacity)    //顺序表空间满时倍增容量
            recap(2 * length);
        data[length] = e;        //添加元素e
        length++;            //长度增1
    }

    int Getlength()        //求顺序表的长度
    {
        return length;
    }

    bool GetElem(int i, T &e)    //求序号i的元素值
    {
        if (i < 0 || i >= length)
            return false;        //参数错误时返回false
        e = data[i];            //取元素值
        return true;                //成功找到元素时返回true
    }

    bool SetElem(int i, T e)        //设置序号i的元素值
    {
        if (i <= 0 || i >= length)        //参数错误时返回false
            return false;
        data[i] = e;
        return true;
    }

    int GetNo(T e)                 //查找第一个为e的元素的序号
    {
        int i = 0;
        while (i < length && data[i] != e)
            i++;                 //查找元素e
        if (i >= length)             //未找到时返回-1
            return -1;
        else
            return i;                 //找到后返回其序号
    }

    bool Insert(int i, T e)        //在线性表中序号i位置插入元素e
    {
        if (i < 0 || i > length)        //参数i错误返回false
            return false;
        if (length == capacity)        //满时倍增容量
            recap(2 * length);
        for (int j = length; j > i; j--)        //data[i]及后元素后移一个位置
            data[j] = data[j - 1];
        data[i] = e;                //插入元素e
        length++;                //长度增1
        return true;
    }

    bool Delete(int i)            //在线性表中删除序号i的元素
    {
        if (i < 0 || i >= length)        //参数i错误返回false
            return false;
        for (int j = i; j < length - 1; j++)
            data[j] = data[j + 1];        //将data[i]之后元素前移一个位置
        length--;                //长度减1
        if (capacity > init_cap && length <= capacity / 4)
            recap(capacity / 2);        //满足缩容条件则容量减半
        return true;
    }

    void DispList()               //输出顺序表L中所有元素
    {
        for (int i = 0; i < length; i++)       //遍历顺序表中各元素值
            cout << data[i] << " ";
        cout << endl;
    }
};

template<typename T>
void Reverse(SqList<T> &L)        //求解算法
{
    int i = 0, j = L.length - 1;
    while (i < j) {
        swap(L.data[i], L.data[j]);      //序号i和j的两个元素交换
        i++;
        j--;
    }
}

template<typename T>
bool Deletek(SqList<T> &L, int i, int k)        //求解算法
{
    if (i < 0 || k < 1 || i + k < 1 || i + k > L.length)
        return false;                //参数i和k错误返回false
    for (int j = i + k; j < L.length; j++)                 //删除k个元素
        L.data[j - k] = L.data[j];
    L.length -= k;                         //长度减k
    return true;
}

template<typename T>
void Deletex1(SqList<T> &L, int x)      //求解算法1
{
    int k = 0;
    for (int i = 0; i < L.length; i++)
        if (L.data[i] != x)          //将不为x的元素插入到data中
        {
            L.data[k] = L.data[i];
            k++;
        }
    L.length = k;              //重置L的长度为k
}

template<typename T>
void Deletex2(SqList<T> &L, int x)    //求解算法2
{
    int k = 0;                //累计等于x的元素个数
    for (int i = 0; i < L.length; i++)
        if (L.data[i] != x)                //将不为x的元素前移k个位置
            L.data[i - k] = L.data[i];
        else                //累计删除的元素个数k
            k++;
    L.length -= k;                    //将L的长度减少k
}

template<typename T>
void Deletex3(SqList<T> &L, int x)        //求解算法3
{
    int i = -1, j = 0;
    while (j < L.length)            //j遍历所有元素
    {
        if (L.data[j] != x)            //找到不为x的元素a[j]
        {
            i++;                //扩大不为x的区间
            if (i != j)
                swap(L.data[i], L.data[j]);    //序号i和j的两个元素交换
        }
        j++;                //继续遍历
    }
    L.length = i + 1;                //将L的长度置为i+1
}

template<typename T>
void Merge2(SqList<T> A, SqList<T> B, SqList<T> &C) {
    int i = 0, j = 0;                     //i用于遍历A,j用于遍历B
    while (i < A.length && j < B.length)          //两个表均没有遍历完毕
    {
        if (A.data[i] < B.data[j]) {
            C.Add(A.data[i]);                 //归并A[i]:将较小的A[i]添加到C中
            i++;
        } else                //归并B[j]:将较小的B[j]添加到C中
        {
            C.Add(B.data[j]);
            j++;
        }
    }
    while (i < A.length)            //若A没有遍历完毕
    {
        C.Add(A.data[i]);                 //归并A中剩余元素
        i++;
    }
    while (j < B.length)            //若B没有遍历完毕
    {
        C.Add(B.data[j]);                 //归并B中剩余元素
        j++;
    }
}

template<typename T>
T Middle(SqList<T> A, SqList<T> B)           //求解算法
{
    int i = 0, j = 0;                   //i,j分别遍历A和B
    int k = 0;                   //累计归并的次数
    while (i < A.length && j < B.length)           //两个有序顺序表均没有遍历完
    {
        k++;                   //归并次数增1
        if (A.data[i] < B.data[j])           //A中当前元素为较小的元素
        {
            if (k == A.length)               //恰好归并了n次
                return A.data[i];           //返回A中的当前元素
            i++;
        } else                   //B中当前元素为较小的元素
        {
            if (k == B.length)               //恰好归并了n次
                return B.data[j];           //返回B中的当前元素
            j++;
        }
    }
}


int main() {
    int i, e;
    SqList<int> L;  //建立类型为int的顺序表对象L
    cout << "创建整数顺序表L" << endl;
    L.Insert(0, 2);    //插入元素2
    L.Insert(1, 3);    //插入元素3
    L.Insert(2, 1);    //插入元素1
    L.Insert(3, 5);    //插入元素5
    L.Insert(4, 4);    //插入元素4
    L.Insert(5, 1);    //插入元素1
    L.Add(8);        //添加整数8
    cout << "顺序表L:";
    L.DispList();
    cout << "长度:" << L.length << "  容量:"
         << L.capacity << endl;
    i = 3;
    L.GetElem(i, e);
    cout << "序号为" << i << "的元素:" << e << endl;
    e = 1;
    cout << "第一个" << e << "的元素序号=" <<
         L.GetNo(e) << "\n";
    i = 2;
    cout << "删除序号为" << i << "的元素\n";
    L.Delete(i);
    cout << "顺序表L:";
    L.DispList();
    cout << "长度:" << L.length << "  容量:"
         << L.capacity << endl;
    int b[] = {0, 1, 1, 0, 1};
    for (int j: b) {
        cout << "删除序号为" << j << "的元素\n";
        L.Delete(j);
        cout << "顺序表L:";
        L.DispList();
        cout << "长度:" << L.length << "  容量:"
             << L.capacity << endl;
    }
    cout << "销毁顺序表L" << endl;
    return 0;
}
